|
Within the fields of computer science and linguistics, specifically in the area of formal languages, the Chomsky hierarchy (occasionally referred to as Chomsky-Schützenberger hierarchy) is a containment hierarchy of classes of formal grammars. This hierarchy of grammars was described by Noam Chomsky in 1956. It is also named after Marcel-Paul Schützenberger, who played a crucial role in the development of the theory of formal languages. == Formal grammars == (詳細はproduction rules'' (''left-hand side'' → ''right-hand side''), where each side consists of a sequence of the following symbols: * a finite set of ''nonterminal symbols'' (indicating that some production rule can yet be applied) * a finite set of ''terminal symbols'' (indicating that no production rule can be applied) * a ''start symbol'' (a distinguished nonterminal symbol) A formal grammar defines (or ''generates'') a ''formal language'', which is a (usually infinite) set of finite-length sequences of symbols that may be constructed by applying production rules to another sequence of symbols (which initially contains just the start symbol). A rule may be applied by: replacing an occurrence of the symbols on its left-hand side, with those that appear on its right-hand side. A sequence of rule applications is called a ''derivation''. Such a grammar defines the formal language: all words consisting solely of terminal symbols which can be reached by a derivation from the start symbol. Nonterminals are often represented by uppercase letters, terminals by lowercase letters, and the start symbol by . For example, the grammar with terminals , nonterminals , production rules : → : → ε (where ε is the empty string) : → : → : → : → : → and start symbol , defines the language of all words of the form (i.e. copies of followed by copies of ). The following is a simpler grammar that defines the same language: Terminals , Nonterminals , Start symbol , Production rules : → : → ε As another example, a grammar for a toy subset of English language is given by: ;terminals: ;nonterminals: ;production rules : → : → : → : → : → : → : → : → : → : → : → and start symbol . An example derivation is : → → → → → → → → → → → → → . Other sequences that can be derived from this grammar are: "''ideas hate great linguists''", and "''ideas generate''". While these sentences are nonsensical, they are syntactically correct. A syntactically incorrect sentence ( e.g. "''ideas ideas great hate''") cannot be derived from this grammar. See "Colorless green ideas sleep furiously" for a similar example given by Chomsky in 1957; see Phrase structure grammar and Phrase structure rules for more natural language examples and the problems of formal grammar in that area. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Chomsky hierarchy」の詳細全文を読む スポンサード リンク
|